#include <cstdlib>
#include <cassert>
#include <cstring>
#include <string>
#include <iostream>
#include <ctime>
#include <sys/time.h>
#include <cstdio>
#include "AI.h"
#include "evaluator.h"
#include "MPC.h"

using namespace std;

double time_distribution[NUM_STAGES];
timeval time_start;
double time_alloc;
long long node_count;
bool force_terminate;

void quickSort(int moves[], gameState children[], int score[], int beg, int end)
{
    int t_score, t_m;
    gameState t_gs;
    
    if (end > beg + 1)
    {
        int piv = score[beg], l = beg + 1, r = end;
        while (l < r)
        {
            if (score[l] >= piv)
                l++;
            else
            {
                r--;
                swap(score[l], score[r], t_score);
                swap(children[l], children[r], t_gs);
                swap(moves[l], moves[r], t_m);
            }
        }
        l--;
        swap(score[l], score[beg], t_score);
        swap(children[l], children[beg], t_gs);
        swap(moves[l], moves[beg], t_m);
        quickSort(moves, children, score, beg, l);
        quickSort(moves, children, score, r, end);
    }
}


int MinimaxEndGame(gameState node, BoardState player, int alpha, int beta, int stage,
                     BitBoard blocked, int lastmove)
{
    // force termination when time runs out
    if (force_terminate)
        return player == WHITE ? INFINITY : -INFINITY;
        
    node_count++;
    // check the time for every 100 nodes searched
    if (node_count % 1000 == 0)
    {
        timeval tp;
        gettimeofday(&tp, NULL);
        
        double elapsed = tp.tv_sec - time_start.tv_sec + 1e-6 * (tp.tv_usec - time_start.tv_usec);
        
        if (time_alloc - elapsed < 0.01)
        {
            //cerr << "time taken: " << elapsed << endl;
            force_terminate = true;
            return (player == WHITE ? INFINITY : -INFINITY);
        }
    }
    
    if (stage == 92)
        return evaluateTerminal(node);
    
    int moves[100];
    BitBoard effects[100];
    int best_move = -1;
    int mCount = getMoves(node, blocked, player, moves, effects);
    
    BoardState next_player = player == WHITE ? BLACK : WHITE;
    if (mCount == 0)
    {
        if (lastmove == -1)
            return evaluateTerminal(node);
        else
            return MinimaxEndGame(node, next_player, alpha, beta, stage, blocked, -1);
    }
    
    // increment stage count
    stage++;
    // build list of children
    gameState children[100];
    for (int i = 0; i < mCount; i++)
        children[i] = applyMove(node, player, moves[i], effects[moves[i]]); 
    
    OrderMoves(moves, children, mCount, player, blocked, stage, -1, stage > END_GAME_TRIVIAL);
    
    // perform minimax search
    for (int i = 0; i < mCount; i++)
    {
        int score = MinimaxEndGame(children[i], next_player, alpha, beta, stage, blocked, moves[i]);
       
        if (score > alpha && player == WHITE) 
        {
            best_move = moves[i];
            alpha = score;
        }
        else if (score < beta && player == BLACK)
        {
            best_move = moves[i];
            beta = score;
        }
        
        if (alpha >= beta) 
            return (player == WHITE ? alpha : beta);
    }
                
    return (player == WHITE ? alpha : beta);
}

/* solve the end game */
int SolveEndGame(gameState gs, BoardState player, BitBoard blocked, int stage, int lastmove)
{
    int moves[100];
    BitBoard effects[100];
    int mCount = getMoves(gs, blocked, player, moves, effects);
    
    int best_move = -1;
    int alpha = -INFINITY;
    int beta = INFINITY;
    BoardState next_player = player == WHITE ? BLACK : WHITE;

    
    // build list of children
    stage++;
    gameState children[100];
    for (int i = 0; i < mCount; i++)
        children[i] = applyMove(gs, player, moves[i], effects[moves[i]]); 
    
    OrderMoves(moves, children, mCount, player, blocked, stage, -1, stage > END_GAME_TRIVIAL);
    
    for (int i = 0; i < mCount; i++)
    {   
        int score = MinimaxEndGame(children[i], next_player, alpha, beta, stage, blocked, moves[i]);
        
        if (score > alpha && player == WHITE) 
        {
            best_move = moves[i];
            alpha = score;
        }
        else if (score < beta && player == BLACK)
        {
            best_move = moves[i];
            beta = score;
        }
        
        if (alpha >= beta) 
            break;
    }
    return best_move;
}

/* order moves
   #in, out# moves      ... input list of moves and output a reordered list
   #in, out# child      ... child game after each move has been applied
   #in#      mCount     ... number of moves
   #in#      player     ... the current player
   #in#      stage      ... stage the game is at 
   #in#      bestmove   ... best move previously found (-1 if does not exist)
   #in#      trivial    ... the ordering is trivial (only uses refutation)    */
void OrderMoves(int moves[], gameState children[], int mCount, BoardState player,
                BitBoard blocked, int stage, int bestmove, bool trivial)
{
    int start = 0;
    int t_m;
    gameState t_gs;
    
    if (bestmove != -1)
    {
        int index = getMoveIndex(bestmove, moves, mCount);
        if (index != -1)
        {
            swap(children[0], children[index], t_gs);
            swap(moves[0], moves[index], t_m);
            start++;
            //cerr << "using best move first wrong" << endl;
        }
    }
    
    if (!trivial)
    {
        int score[100];
        for (int i = start; i < mCount; i++)
        {
            if (player == WHITE)
                score[i] = evaluateGame(children[i], blocked, player, stage);
            else
                score[i] = -evaluateGame(children[i], blocked, player, stage);
            
        }
        quickSort(moves, children, score, start, mCount);
    } 
}

int LOOKUP;
int HIT;

/* Compute minimax score for the node
   #in#  node       ... current game state
   #in#  player     ... player to move
   #in#  depth      ... depth of the subtree
   #in#  alpha      ... lower bound for optimum score

   #in#  beta       ... upper bound for optimum score
   #in#  stage      ... which stage the game is at (= number of pieces - 5)
   #in#  lastmove   ... the opponent's last move (-1 for no move)
   return           ... minimax score of the current node                   */
int Minimax(gameState node, BoardState player, int depth, int alpha, int beta, 
              int stage, BitBoard blocked, int lastmove)
{
    // force termination when time runs out
    if (force_terminate)
        return player == WHITE ? INFINITY : -INFINITY;
        
    node_count++;
    // check the time for every 100 nodes searched
    if (node_count % 1000 == 0)
    {
        timeval tp;
        gettimeofday(&tp, NULL);
        
        double elapsed = tp.tv_sec - time_start.tv_sec + 1e-6 * (tp.tv_usec - time_start.tv_usec);
        
        //cerr << time_alloc << elapsed << endl;
        if (time_alloc - elapsed < 0.01)
        {
            //cerr << "time taken: " << elapsed << endl;
            force_terminate = true;
            return (player == WHITE ? INFINITY : -INFINITY);
        }
    }
    
    // reached terminal state or leaf node
    if (stage == 92)
        return evaluateTerminal(node);
    if (depth <= 0)
        return evaluateGame(node, blocked, player, stage);
    
    int moves[100];
    int best_move = -1;
    BitBoard effects[100];
    gameState children[100];
    
    // key and lock for the transposition table
    U64 key = 0;
    U64 lock = 0;
    int hash_type = player == WHITE ? ALPHA : BETA;
    if (depth >= TRIVIAL_DEPTH - 1)
    {
        key = GetKey(node);
        lock = GetLock(node);
        
        TTEntry * tt = getTT(key, lock);
        
        LOOKUP++;
        
        if (tt != NULL)
        {
            HIT++;
            if (tt->depth >= depth && tt->type == ALPHA && tt->value > beta)
                return tt->value;
            else if (tt->depth >= depth && tt->type == BETA && tt->value < alpha)
                return tt->value;
            else if (tt->depth >= depth && tt->type == EXACT)
                return tt->value;
                
            best_move = tt->best_move;
        }
    }
    
    /*
    // try trim nodes by performing shallow search first
    if (depth == PAIR1_DEEP || depth == PAIR2_DEEP)
    {
        int shallow = (depth == PAIR1_DEEP ? PAIR1_SHALLOW : PAIR2_SHALLOW);
        
        int bound = GetBoundLow(alpha, stage, shallow) ;
        if (bound != 0 && Minimax(node, player, shallow, bound, bound+1, stage, blocked, lastmove) <= bound)
        {
            return alpha;
        }
        bound = GetBoundHigh(beta, stage, shallow);
        if (bound != 0 && Minimax(node, player, shallow, bound-1, bound, stage, blocked, lastmove) >= bound)
        {
            return beta;
        }
    }
    */
    
    
    int mCount = getMoves(node, blocked, player, moves, effects);
    BoardState next_player = player == BLACK ? WHITE : BLACK;
    
    // if current player has no move
    if (mCount == 0)
    {
        // neither player has move, we reached terminal position
        if (lastmove == -1)
            return evaluateTerminal(node);
        else
            return Minimax(node, next_player, depth, alpha, beta, stage, blocked, -1);
    }
    
    // build children
    stage++;
    for (int i = 0; i < mCount; i++)
    {
        children[i] = applyMove(node, player, moves[i], effects[moves[i]]);
    }
   
    OrderMoves(moves, children, mCount, player, blocked, stage, best_move, depth < TRIVIAL_DEPTH);
    
    // otherwise
    depth--;
    for (int i = 0; i < mCount; i++)
    {
        int score = Minimax(children[i], next_player, depth, alpha, beta, stage, blocked, moves[i]);
        
        if (player == WHITE && score > alpha)
        {
            hash_type = EXACT;
            alpha = score;
            best_move = moves[i];
        }
        else if (player == BLACK && score < beta)
        {
            hash_type = EXACT;
            beta = score;
            best_move = moves[i];
        }
        
        if (alpha >= beta)
        {
            if (player == WHITE)
            {
                if (key != 0)
                    storeTT(key, lock, ALPHA, alpha, depth+1, best_move);
                return alpha;
            }
            else
            {
                if (key != 0)
                    storeTT(key, lock, BETA, beta, depth+1, best_move);
                return beta;
            }
        }
    }
    
    if (player == WHITE)
    {
        if (key != 0)
            storeTT(key, lock, hash_type, alpha, depth+1, best_move);
        return alpha;
    }
    else
    {
        if (key != 0)
            storeTT(key, lock, hash_type, beta, depth+1, best_move);
        return beta;
    }
}

/* choose the best move 
   #in#  board      ... current board state
   #in#  player     ... current player
   return           ... best move (x, y) in the format x*10 + y             */
int chooseMove(Board & board, BoardState player, int depth, int end_game, int lastmove, bool * full)
{
    int moves[100], mCount, stage;
    BitBoard effects[100];
    
    int best_move = 0;
    BitBoard blocked;
    
    gameState gs = parseBoard(board, blocked);
    
    initialiseBoardSpecific(blocked);

    stage = BitCount(gs.white | gs.black) - 5;
    
    force_terminate = false;
    node_count = 0;
     
        
    if (full != NULL)
        *full = false;
          
    if (stage >= 91 - end_game)
    {
        int move = SolveEndGame(gs, player, blocked, stage, lastmove);
        if (!force_terminate && full != NULL)
            *full = true;
        return move;
    }
    
    mCount = getMoves(gs, blocked, player, moves, effects);
    int alpha = -INFINITY;
    int beta = INFINITY;
    BoardState next_player = player == WHITE ? BLACK : WHITE;
    
    U64 key = 0;
    U64 lock = 0;
    int hash_type = player == WHITE ? ALPHA : BETA;
    if (depth >= TRIVIAL_DEPTH - 1)
    {
        key = GetKey(gs);
        lock = GetLock(gs);
        
        LOOKUP++;
        
        TTEntry * tt = getTT(key, lock);
        
        if (tt != NULL)
        {
            HIT++;
            best_move = tt->best_move;
        }
    }
        
    
    // build children
    gameState children[100];
    for (int i = 0; i < mCount; i++)
    {
        children[i] = applyMove(gs, player, moves[i], effects[moves[i]]);
    }
    
    stage++;
    OrderMoves(moves, children, mCount, player, blocked, stage, best_move, depth < TRIVIAL_DEPTH);
    
    depth--;   
    for (int i = 0; i < mCount; i++)
    {
        int score = Minimax(children[i], next_player, depth, alpha, beta, stage, blocked, moves[i]);
        
        if (player == WHITE && score > alpha)
        {
            hash_type = EXACT;
            alpha = score;
            best_move = moves[i];
        }
        else if (player == BLACK && score < beta)
        {
            hash_type = EXACT;
            beta = score;
            best_move = moves[i];
        }
        
        if (alpha >= beta)
            break;
    }

    if (player == WHITE)
    {
        if (key != 0)
            storeTT(key, lock, hash_type, alpha, depth+1, best_move);
    }
    else
    {
        if (key != 0)
            storeTT(key, lock, hash_type, beta,  depth+1, best_move);
    }
    
    //cout << cut_count << "/" << enter_count << " nodes cut\n";
	return best_move;
}

/* assign time for this stage */ 
double CalculateAllocatedTime(double remain, int stage)
{
    double sum = 0;
    for (int i = stage; i < NUM_STAGES; i++)
        sum += time_distribution[i];
    
    return remain * time_distribution[stage] / sum;
}

/* choose the best move using variable depth + iterative deepening */
int chooseMove2(Board & board, BoardState player, double time_remaining)
{
    LOOKUP = HIT = 0;
    
    BitBoard blocked;
    gameState gs = parseBoard(board, blocked);
    
    static int misses = 0;
    static double left_over = 0;
    
    int best_move;
    // initialise best_move to random
    const set<pair<int, int> > moves = board.legalMoves(player);
    assert(!moves.empty());
    int randomIndex = (int)(drand48() * moves.size());
    set<pair<int, int> >::const_iterator it = moves.begin();
    while (randomIndex-- > 0) {
        ++it;
    }
    best_move = it->first + it->second * 10;
    
    // calculate current time and time allocated for this move
    gettimeofday(&time_start, NULL);
    
    int stage = BitCount(gs.white | gs.black) - 4;
    time_alloc = CalculateAllocatedTime(time_remaining, stage) + left_over;
    
    cerr << "allocated time: " << time_alloc << endl;
    
    if (stage == 0 || stage == 1)
        misses = 0;
    
    // infinite loop for iterative deepening, break when time's up
    int depth = 1;
    int end_game_depth = 5;
    double prev, elapsed, current;
    bool full;
    prev = 0.0;
    elapsed = 0.0;
    while (true)
    {   
        // perform search and record time taken
        timeval tp1, tp2;
        gettimeofday(&tp1, NULL);
        
        int m = chooseMove(board, player, depth, end_game_depth, -1, &full);
        
        if (!force_terminate && board.checkMove(m%10, m/10, player))
        {   
            depth++;
            end_game_depth++;
            best_move = m;
        }
        else
            misses++;
        
        // time taken from this search
        gettimeofday(&tp2, NULL);
        
        current = (tp2.tv_sec - tp1.tv_sec) + 1e-6 * (tp2.tv_usec - tp1.tv_usec);
        
        left_over = time_alloc - current - elapsed;
        
        // exit the loop if there is insufficient time for the next iteration        
        if (prev != 0 && current * current / prev / 3 > left_over)
            break;
        if (full)
            break;
        if (force_terminate)
            break;
            
        prev = current;
        elapsed += prev;
    }
    end_game_depth--;
    depth--;
    if (full)
        depth = end_game_depth;
        
    printf("stage %2d depth %2d, misses: %d/%d\n", stage, depth, misses, stage+1);
    printf("transposition hits %d/%d\n", HIT, LOOKUP);
    cerr << "left_over time: " << left_over << endl;
    
    return best_move;
}

void initialiseAI()
{
    force_terminate = false;
    gettimeofday(&time_start, NULL);
    time_alloc = 1000;
    
    for (int i = 0; i < NUM_STAGES; i++)
    {  
        if (i < 40)
            time_distribution[i] = 100;   
        else if (i < 50)
            time_distribution[i] = 80;   
        else if (i < 60)
            time_distribution[i] = 80;   
        else if (i < 70)
            time_distribution[i] = 64;   
        else if (i < 78)
            time_distribution[i] = 64;   
        else if (i < 85)
            time_distribution[i] = 4; 
        else
            time_distribution[i] = 1;    
    }
    
    initialiseMasks();
    InitialiseMPC();
    initialiseEvaluator();
}
